﻿#include"BTNode.h"


/*
// 编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 
// 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。
// 建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
BinaryTreeNode* ConstructBinaryTree(char* parr, int* i)
{
	if (parr[*i] == '#')
	{
		(*i)++;
		return NULL;
	}

	BinaryTreeNode* node = BuyNode(parr[(*i)++]);
	node->left = ConstructBinaryTree(parr, i);
	node->right = ConstructBinaryTree(parr, i);
	return node;
}
int main() 
{
	char prevArr[] = "12##4##";
	int i = 0;

	BinaryTreeNode* root = ConstructBinaryTree(prevArr, &i);

	InOrder(root);

	return 0;
}
*/








int main()
{
	BinaryTreeNode* root = CreatBinaryTree();

	// 前序遍历
	PrevOrder(root); printf("\n");

	// 中序遍历
	InOrder(root); printf("\n");

	// 后序遍历
	PostOrder(root); printf("\n");

	// 节点个数
	printf("节点个数：%d\n", BinaryTreeSize(root));

	// 叶子节点个数
	printf("叶子节点个数：%d\n", BinaryTreeLeafSize(root));

	// 二叉树的高度
	printf("二叉树的高度：%d\n", BinaryTreeHeight(root));

	// 第一层节点个数
	printf("第一层节点个数：%d\n", BinaryTreeLevelKSize(root, 1));
	// 第二层节点个数
	printf("第二层节点个数：%d\n", BinaryTreeLevelKSize(root, 2));
	// 第三层节点个数
	printf("第三层节点个数：%d\n", BinaryTreeLevelKSize(root, 3));

	// 查找值为1的节点并返回该节点
	BinaryTreeNode* findroot = BinaryTreeFind(root, 1);
	if (findroot != NULL)
		printf("x为1的节点：x=%d\n", findroot->data);

	// 查找值为3的节点并返回该节点
	findroot = BinaryTreeFind(root, 3);
	if (findroot != NULL)
		printf("x为3的节点：x=%d\n", findroot->data);

	// 层序遍历
	printf("层序遍历：");
	LevelOrder(root);

	// 判断二叉树是否是完全二叉树
	printf("当前二叉树是否是完全二叉树：");
	if (BinaryTreeComplete(root))printf("Yes\n"); else printf("No\n");

	// 释放二叉树
	BinaryTreeDestroy(root);
	root = NULL;

	return 0;
}







/*
// 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
// 如果存在，返回 true ；否则，返回 false 。
bool isSameTree(BinaryTreeNode* p, BinaryTreeNode* q)
{
	if (p == NULL && q == NULL)
		return true;

	if (q == NULL || p == NULL)
		return false;

	if (p->data != q->data)
		return false;

	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
bool isSubtree(BinaryTreeNode* root, BinaryTreeNode* subRoot)
{
	if (root == NULL)
		return false;

	if (isSameTree(root, subRoot))
		return true;

	return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
int main()
{
	BinaryTreeNode* n1 = BuyNode(1); assert(n1);
	BinaryTreeNode* n2 = BuyNode(1); assert(n1);
	n1->left = n2;

	BinaryTreeNode* m1 = BuyNode(1); assert(n1);

	bool ret = isSubtree(n1, m1);
	if (ret)
		printf("d");

	return 0;
}
*/







/*
// 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
int BTreeSize(BinaryTreeNode* root)
{
	if (root == NULL)
		return 0;

	return BTreeSize(root->left) + BTreeSize(root->right) + 1;
}
void _preorderTraversal(BinaryTreeNode* root, int* PrevOrderArr, int* pi)
{
	if (root == NULL)
		return;

	PrevOrderArr[(*pi)++] = root->data;
	_preorderTraversal(root->left, PrevOrderArr, pi);
	_preorderTraversal(root->right, PrevOrderArr, pi);
}
int* preorderTraversal(BinaryTreeNode* root, int* returnSize)
{
	if (root == NULL)
		return NULL;

	*returnSize = BTreeSize(root);
	int* PrevOrderArr = (int*)malloc(sizeof(int) * (*returnSize));
	if (PrevOrderArr == NULL)
	{
		perror("preorderTraversal.malloc");
		return NULL;
	}
	
	int i = 0;
	_preorderTraversal(root, PrevOrderArr, &i);

	return PrevOrderArr;
}
int main()
{
	BinaryTreeNode* root = CreatBinaryTree();
	
	int retArrSize = 0;
	int* retArr = preorderTraversal(root, &retArrSize);
	for (int i = 0; i < retArrSize; i++)
		printf("%d ", retArr[i]);

	return 0;
}
*/






/*
// 给你一个二叉树的根节点 root ， 检查它是否轴对称。
bool _isSymmetric(BinaryTreeNode* leftRoot, BinaryTreeNode* rightRoot)
{
	if (leftRoot == NULL && rightRoot == NULL)
		return true;

	if (leftRoot == NULL || rightRoot == NULL)
		return false;

	if (leftRoot->data != rightRoot->data)
		return false;

	return _isSymmetric(leftRoot->left, rightRoot->right) && _isSymmetric(leftRoot->right, rightRoot->left);
}
bool isSymmetric(BinaryTreeNode* root)
{
	if (root == NULL)
		return true;

	return _isSymmetric(root->left, root->right);
}
int main()
{
	BinaryTreeNode* root = CreatBinaryTree();
	if (isSymmetric(root))
		printf("isSymmetric\n");

	return 0;
}
*/






/*
// 如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false
bool isUnivalTree(BinaryTreeNode* root)
{
	if (root == NULL)
		return true;

	if ((root->left != NULL && root->data != root->left->data) || (root->right != NULL && root->data != root->right->data))
		return false;

	return isUnivalTree(root->left) && isUnivalTree(root->right);
}
int main()
{
	BinaryTreeNode* root = CreatBinaryTree();
	if (isUnivalTree(root))
		printf("isUnivalTree\n");

	return 0;
}
*/







/*
// 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
bool isSameTree(struct BinaryTreeNode* p, struct BinaryTreeNode* q)
{
	if (p == NULL && q == NULL)
		return true;

	if (p != NULL && q == NULL || p == NULL && q != NULL)
		return false;

	if (p->data != q->data)
		return false;

	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
int main()
{
	BinaryTreeNode* root1 = CreatBinaryTree();
	BinaryTreeNode* root2 = CreatBinaryTree();

	printf("%d\n", isSameTree(root1, root2));

	return 0;
}
*/












